\hypertarget{BigInt_8h}{
\section{Source/BigInt.h File Reference}
\label{BigInt_8h}\index{Source/BigInt.h@{Source/BigInt.h}}
}
FASTER THAN GMP, ALMOST.  


{\tt \#include $<$stdbool.h$>$}\par
{\tt \#include $<$stdint.h$>$}\par


Include dependency graph for BigInt.h:\nopagebreak
\begin{figure}[H]
\begin{center}
\leavevmode
\includegraphics[width=80pt]{BigInt_8h__incl}
\end{center}
\end{figure}


This graph shows which files directly or indirectly include this file:\nopagebreak
\begin{figure}[H]
\begin{center}
\leavevmode
\includegraphics[width=145pt]{BigInt_8h__dep__incl}
\end{center}
\end{figure}
\subsection*{Data Structures}
\begin{CompactItemize}
\item 
struct \textbf{BigInt}
\end{CompactItemize}
\subsection*{Typedefs}
\begin{CompactItemize}
\item 
\hypertarget{BigInt_8h_17b4f15feb9a9bc1400293d6e20cb3a3}{
typedef uint8\_\-t \textbf{BigInt\_\-Digit}}
\label{BigInt_8h_17b4f15feb9a9bc1400293d6e20cb3a3}

\end{CompactItemize}
\subsection*{Functions}
\begin{CompactItemize}
\item 
\hypertarget{BigInt_8h_b0d0305431da56f27a8eac6c5df8d81a}{
void \textbf{BigInt\_\-NthRoot} (BigInt $\ast$Result, BigInt Number, BigInt Root)}
\label{BigInt_8h_b0d0305431da56f27a8eac6c5df8d81a}

\item 
\hypertarget{BigInt_8h_01d32eaad6fa159a24abc70a14e24e2e}{
void \textbf{BigInt\_\-Random} (BigInt $\ast$Result, BigInt Min, BigInt Max)}
\label{BigInt_8h_01d32eaad6fa159a24abc70a14e24e2e}

\item 
\hypertarget{BigInt_8h_9eca3c15af79b4341c3323c5d0614b18}{
BigInt \textbf{BigInt\_\-Create} ()}
\label{BigInt_8h_9eca3c15af79b4341c3323c5d0614b18}

\item 
\hypertarget{BigInt_8h_f349bda1e82bea9b189ac70e6f1a3146}{
void \textbf{BigInt\_\-Destroy} (BigInt BigInt)}
\label{BigInt_8h_f349bda1e82bea9b189ac70e6f1a3146}

\item 
\hypertarget{BigInt_8h_9bc73aabd8be639ce0b09b730e200e92}{
void \textbf{BigInt\_\-SetFromInt} (BigInt $\ast$BigInt, int Value)}
\label{BigInt_8h_9bc73aabd8be639ce0b09b730e200e92}

\item 
\hypertarget{BigInt_8h_53a0104c5b8ec5367f680dc18a98a0f6}{
void \textbf{BigInt\_\-SetFromLong} (BigInt $\ast$BigInt, long Value)}
\label{BigInt_8h_53a0104c5b8ec5367f680dc18a98a0f6}

\item 
\hypertarget{BigInt_8h_9634699b077950cbf014514139e22b44}{
void \textbf{BigInt\_\-SetFromBigInt} (BigInt $\ast$Output, BigInt Value)}
\label{BigInt_8h_9634699b077950cbf014514139e22b44}

\item 
\hypertarget{BigInt_8h_a2514e4e68731f7445ce2a25fbde3871}{
void \textbf{BigInt\_\-Inc} (BigInt $\ast$Number)}
\label{BigInt_8h_a2514e4e68731f7445ce2a25fbde3871}

\item 
\hypertarget{BigInt_8h_e23b92dea5a1ef7ccfb7e765bc9785b8}{
void \textbf{BigInt\_\-Dec} (BigInt $\ast$Number)}
\label{BigInt_8h_e23b92dea5a1ef7ccfb7e765bc9785b8}

\item 
\hypertarget{BigInt_8h_2cc08fb47e321aae05c68efd7010ad6d}{
void \textbf{BigInt\_\-Negate} (BigInt $\ast$Number)}
\label{BigInt_8h_2cc08fb47e321aae05c68efd7010ad6d}

\item 
\hypertarget{BigInt_8h_692d4bd24596c6e686b217f04defb09b}{
void \textbf{BigInt\_\-Add} (BigInt $\ast$Result, BigInt Number0, BigInt Number1)}
\label{BigInt_8h_692d4bd24596c6e686b217f04defb09b}

\item 
\hypertarget{BigInt_8h_a07a076c3ac402c7df6b4e9af32d7d81}{
void \textbf{BigInt\_\-Sub} (BigInt $\ast$Result, BigInt Number0, BigInt Number1)}
\label{BigInt_8h_a07a076c3ac402c7df6b4e9af32d7d81}

\item 
\hypertarget{BigInt_8h_f1078f5b27764acad06b22b7bfebc8ad}{
void \textbf{BigInt\_\-Resize} (BigInt $\ast$BigInt)}
\label{BigInt_8h_f1078f5b27764acad06b22b7bfebc8ad}

\item 
\hypertarget{BigInt_8h_3a7d1107e28632a60540d14b5a5a5568}{
void \textbf{BigInt\_\-Div} (BigInt $\ast$Result, BigInt Number0, BigInt Number1)}
\label{BigInt_8h_3a7d1107e28632a60540d14b5a5a5568}

\item 
\hypertarget{BigInt_8h_1fb70df4b9c26f564631747d94446c06}{
void \textbf{BigInt\_\-Mod} (BigInt $\ast$Result, BigInt Number0, BigInt Number1)}
\label{BigInt_8h_1fb70df4b9c26f564631747d94446c06}

\item 
\hypertarget{BigInt_8h_007ded5502efb0cd1be1d7d2254b9b90}{
void \textbf{BigInt\_\-Sqrt} (BigInt $\ast$Result, BigInt Number)}
\label{BigInt_8h_007ded5502efb0cd1be1d7d2254b9b90}

\item 
\hypertarget{BigInt_8h_4063909d889b4ff3355f570b078a614a}{
void \textbf{BigInt\_\-Pow} (BigInt $\ast$Result, BigInt Base, BigInt Exponent)}
\label{BigInt_8h_4063909d889b4ff3355f570b078a614a}

\item 
\hypertarget{BigInt_8h_1bea60872266a72392f91337834c7a1d}{
void \textbf{BigInt\_\-Factorial} (BigInt $\ast$Result, BigInt Number)}
\label{BigInt_8h_1bea60872266a72392f91337834c7a1d}

\item 
\hypertarget{BigInt_8h_da59fb4265f6aebaa56b408867d79edd}{
int \textbf{BigInt\_\-IsEqualTo} (BigInt Number0, BigInt Number1)}
\label{BigInt_8h_da59fb4265f6aebaa56b408867d79edd}

\item 
\hypertarget{BigInt_8h_73a14326cc8f7a42b1d5dfc84a2fcdc8}{
int \textbf{BigInt\_\-IsNotEqualTo} (BigInt Number0, BigInt Number1)}
\label{BigInt_8h_73a14326cc8f7a42b1d5dfc84a2fcdc8}

\item 
\hypertarget{BigInt_8h_98740c6596df9b105a9b30b2e8997dbf}{
int \textbf{BigInt\_\-IsLessThan} (BigInt Number0, BigInt Number1)}
\label{BigInt_8h_98740c6596df9b105a9b30b2e8997dbf}

\item 
\hypertarget{BigInt_8h_a6f1d3b8f3d40f16ce37c878d55b9e91}{
int \textbf{BigInt\_\-IsLessThanOrEqualTo} (BigInt Number0, BigInt Number1)}
\label{BigInt_8h_a6f1d3b8f3d40f16ce37c878d55b9e91}

\item 
\hypertarget{BigInt_8h_59ae581530fd0880bab61b798f658e51}{
int \textbf{BigInt\_\-IsGreaterThan} (BigInt Number0, BigInt Number1)}
\label{BigInt_8h_59ae581530fd0880bab61b798f658e51}

\item 
\hypertarget{BigInt_8h_e58a518275f5df19432548446464f5c2}{
int \textbf{BigInt\_\-IsGreaterThanOrEqualTo} (BigInt Number0, BigInt Number1)}
\label{BigInt_8h_e58a518275f5df19432548446464f5c2}

\item 
\hypertarget{BigInt_8h_7d32611353d520511587ac5db598022e}{
int \textbf{BigInt\_\-GetDecimalLength} (BigInt Number)}
\label{BigInt_8h_7d32611353d520511587ac5db598022e}

\item 
\hypertarget{BigInt_8h_555b9e7a93d5629d29b565ce6931a39a}{
void \textbf{BigInt\_\-GetAsString} (BigInt Number, char $\ast$String)}
\label{BigInt_8h_555b9e7a93d5629d29b565ce6931a39a}

\item 
\hypertarget{BigInt_8h_6860f2bab43b42c85e5f7c3960bd91fa}{
void \textbf{BigInt\_\-Clean} (BigInt $\ast$Number)}
\label{BigInt_8h_6860f2bab43b42c85e5f7c3960bd91fa}

\item 
\hypertarget{BigInt_8h_bf87cbc227ce80aed5b16344155ca498}{
void \textbf{BigInt\_\-Debug} (BigInt BigInt)}
\label{BigInt_8h_bf87cbc227ce80aed5b16344155ca498}

\item 
\hypertarget{BigInt_8h_9d859d952bd7f331e09d6f0e1ec0fa56}{
void \textbf{BigInt\_\-Abs} (BigInt $\ast$BigInt)}
\label{BigInt_8h_9d859d952bd7f331e09d6f0e1ec0fa56}

\item 
\hypertarget{BigInt_8h_d9d56525c6516f0dad8b1e583604024c}{
void \textbf{BigInt\_\-GCD} (BigInt $\ast$Result, BigInt Number0, BigInt Number1)}
\label{BigInt_8h_d9d56525c6516f0dad8b1e583604024c}

\item 
\hypertarget{BigInt_8h_47ddc2f86f854f747db6e0aa75be9288}{
void \textbf{BigInt\_\-LCM} (BigInt $\ast$Result, BigInt Number0, BigInt Number1)}
\label{BigInt_8h_47ddc2f86f854f747db6e0aa75be9288}

\item 
\hypertarget{BigInt_8h_33750c45534f073875fad2360ddb2dc8}{
void \textbf{BigInt\_\-SetFromString} (BigInt $\ast$BigInt, char $\ast$Value)}
\label{BigInt_8h_33750c45534f073875fad2360ddb2dc8}

\item 
void \hyperlink{BigInt_8h_2bfc5536241f968094ec5e04cfc67c51}{BigInt\_\-Mul} (BigInt $\ast$Result, BigInt Number0, BigInt Number1)
\item 
void \hyperlink{BigInt_8h_95f7d902ad539c4e868513014307d119}{BigInt\_\-FastMul} (BigInt $\ast$Result, BigInt Number0, BigInt Number1)
\item 
void \hyperlink{BigInt_8h_c32621fd44f345ce54b315ed6f1f310b}{BigInt\_\-SlowMul} (BigInt $\ast$Result, BigInt Number0, BigInt Number1)
\end{CompactItemize}


\subsection{Detailed Description}
FASTER THAN GMP, ALMOST. 

\begin{Desc}
\item[Author:]Daniel White \end{Desc}
\begin{Desc}
\item[Version:]0.1 \end{Desc}
\hypertarget{Vector_8h_Description}{}\subsection{Description}\label{Vector_8h_Description}
(I'll get round to this) asd 

Definition in file \hyperlink{BigInt_8h-source}{BigInt.h}.

\subsection{Function Documentation}
\hypertarget{BigInt_8h_95f7d902ad539c4e868513014307d119}{
\index{BigInt.h@{BigInt.h}!BigInt\_\-FastMul@{BigInt\_\-FastMul}}
\index{BigInt\_\-FastMul@{BigInt\_\-FastMul}!BigInt.h@{BigInt.h}}
\subsubsection[{BigInt\_\-FastMul}]{\setlength{\rightskip}{0pt plus 5cm}void BigInt\_\-FastMul (BigInt $\ast$ {\em Result}, \/  BigInt {\em Number0}, \/  BigInt {\em Number1})}}
\label{BigInt_8h_95f7d902ad539c4e868513014307d119}


Multiples two BigInts together (Number0 and Number1), and stores the result into Result, using the Karatsuba algorithm.

\begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em Result}]A pointer to a Bigint where the result should be stored. \item[{\em Number0}]First number. \item[{\em Number1}]Second number. \end{description}
\end{Desc}
\begin{Desc}
\item[Returns:]\end{Desc}


Definition at line 391 of file BigInt.c.

\begin{Code}\begin{verbatim}392 {
393     if (Number0.IsNegative==true && Number1.IsNegative==false)
394     {
395         BigInt_Negate(&Number0);
396         BigInt_FastMul(Result, Number0, Number1);
397         BigInt_Negate(Result);
398         BigInt_Negate(&Number0);
399         return;
400     }
401     if (Number0.IsNegative==false && Number1.IsNegative==true)
402     {
403         BigInt_Negate(&Number1);
404         BigInt_FastMul(Result, Number0, Number1);
405         BigInt_Negate(Result);
406         BigInt_Negate(&Number1);
407         return;
408     }
409     if (Number0.IsNegative==true && Number1.IsNegative==true)
410     {
411         BigInt_Negate(&Number0);
412         BigInt_Negate(&Number1);
413         BigInt_FastMul(Result, Number0, Number1);
414         BigInt_Negate(&Number0);
415         BigInt_Negate(&Number1);
416         return;
417     }
418     if (BigInt_IsGreaterThan(Number1, Number0))
419     {
420         BigInt_FastMul(Result, Number1, Number0);
421         return;
422     }
423     
424     /*
425     X=X1*10^M+X0
426     Y=Y1*10^M+X1
427     
428     Z2=X1*Y1
429     Z0=X0*Y0
430     Z1=(X1+X0)*(Y1+Y0)-Z2-Z0
431     P0=Z0
432     P1=Z1*10^M
433     P2=Z2*10^(2*M)
434     XY=P2+P1+P0
435     */
436     
437     /* Choose M */
438     int M;
439     if (Number0.Length<Number1.Length)
440         M=Number0.Length/2;
441     else
442         M=Number1.Length/2;
443     
444     /* Create X0, X1, Y0 and Y1 */
445     BigInt X0=BigInt_Create(),X1=BigInt_Create(),Y0=BigInt_Create(),Y1=BigInt_Create();
446     
447     X1.Length=Number0.Length-M;
448     X1.Size=X1.Length;
449     X0.Length=M;
450     X0.Size=M;
451     Y1.Length=Number1.Length-M;
452     Y1.Size=Y1.Length;
453     Y0.Length=M;
454     Y0.Size=M;
455     
456     X0.Digits=realloc(X0.Digits, sizeof(BigInt_Digit)*X0.Length);
457     X1.Digits=realloc(X1.Digits, sizeof(BigInt_Digit)*X1.Length);
458     Y0.Digits=realloc(Y0.Digits, sizeof(BigInt_Digit)*Y0.Length);
459     Y1.Digits=realloc(Y1.Digits, sizeof(BigInt_Digit)*Y1.Length);
460     
461     int Position;
462     for(Position=0;Position<M;++Position)
463     {
464         X0.Digits[Position]=Number0.Digits[Position];
465         Y0.Digits[Position]=Number1.Digits[Position];
466     }
467     for(Position=0;Position<X1.Length;++Position)
468         X1.Digits[Position]=Number0.Digits[Position+M];
469     for(Position=0;Position<Y1.Length;++Position)
470         Y1.Digits[Position]=Number1.Digits[Position+M];
471     
472     /* Compute Z2 and Z0 */
473     BigInt Z2=BigInt_Create();
474     BigInt Z0=BigInt_Create();
475     
476     BigInt_Mul(&Z2, X1, Y1);
477     BigInt_Mul(&Z0, X0, Y0);
478     
479     /* Compute Z1 */
480     BigInt Z1=BigInt_Create();
481     BigInt Temp0=BigInt_Create();
482     BigInt Temp1=BigInt_Create();
483     BigInt Temp2=BigInt_Create();
484     
485     BigInt_Add(&Temp0, X0, X1);
486     BigInt_Add(&Temp1, Y0, Y1);
487     BigInt_Mul(&Temp2, Temp0, Temp1);
488     BigInt_Sub(&Temp1, Temp2, Z2);
489     BigInt_Sub(&Z1, Temp1, Z0);
490     
491     /* Work out P0, P1 and P2 */
492     BigInt P0=BigInt_Create();
493     BigInt P1=BigInt_Create();
494     BigInt P2=BigInt_Create();
495     
496     BigInt_SetFromBigInt(&P0, Z0);
497     
498     P1.Length=BigInt_GetDecimalLength(Z1)+M;
499     P2.Length=BigInt_GetDecimalLength(Z2)+2*M;
500     BigInt_Resize(&P1);
501     BigInt_Resize(&P2);
502     
503     for(Position=0;Position<M;++Position)
504         P1.Digits[Position]=0;
505     for(Position=0;Position<2*M;++Position)
506         P2.Digits[Position]=0;
507     for(Position=M;Position<P1.Length;++Position)
508         P1.Digits[Position]=Z1.Digits[Position-M];
509     for(Position=2*M;Position<P2.Length;++Position)
510         P2.Digits[Position]=Z2.Digits[Position-2*M];
511     
512     /* Finally compute XY */
513     BigInt_Add(&Temp0, P0, P1);
514     BigInt_Add(Result, Temp0, P2);  
515     
516     /* Clean up */
517     BigInt_Destroy(X0);
518     BigInt_Destroy(X1);
519     BigInt_Destroy(Y0);
520     BigInt_Destroy(Y1);
521     BigInt_Destroy(Z0);
522     BigInt_Destroy(Z1);
523     BigInt_Destroy(Z2);
524     BigInt_Destroy(Temp0);
525     BigInt_Destroy(Temp1);
526     BigInt_Destroy(Temp2);
527     BigInt_Destroy(P0);
528     BigInt_Destroy(P1);
529     BigInt_Destroy(P2);
530 }
\end{verbatim}
\end{Code}


\hypertarget{BigInt_8h_2bfc5536241f968094ec5e04cfc67c51}{
\index{BigInt.h@{BigInt.h}!BigInt\_\-Mul@{BigInt\_\-Mul}}
\index{BigInt\_\-Mul@{BigInt\_\-Mul}!BigInt.h@{BigInt.h}}
\subsubsection[{BigInt\_\-Mul}]{\setlength{\rightskip}{0pt plus 5cm}void BigInt\_\-Mul (BigInt $\ast$ {\em Result}, \/  BigInt {\em Number0}, \/  BigInt {\em Number1})}}
\label{BigInt_8h_2bfc5536241f968094ec5e04cfc67c51}


Multiples two BigInts together (Number0 and Number1), and stores the result into Result. The algorithm used depends on the operand sizes: for small sized arguments the standard multiplication method is used; for larger arguments, the Karatsuba algorithm is used.

\begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em Result}]A pointer to a Bigint where the result should be stored. \item[{\em Number0}]First number. \item[{\em Number1}]Second number. \end{description}
\end{Desc}
\begin{Desc}
\item[Returns:]\end{Desc}


Definition at line 351 of file BigInt.c.

\begin{Code}\begin{verbatim}352 {
353     if (Number0.IsNegative==true && Number1.IsNegative==false)
354     {
355         BigInt_Negate(&Number0);
356         BigInt_Mul(Result, Number0, Number1);
357         BigInt_Negate(Result);
358         BigInt_Negate(&Number0);
359         return;
360     }
361     if (Number0.IsNegative==false && Number1.IsNegative==true)
362     {
363         BigInt_Negate(&Number1);
364         BigInt_Mul(Result, Number0, Number1);
365         BigInt_Negate(Result);
366         BigInt_Negate(&Number1);
367         return;
368     }
369     if (Number0.IsNegative==true && Number1.IsNegative==true)
370     {
371         BigInt_Negate(&Number0);
372         BigInt_Negate(&Number1);
373         BigInt_Mul(Result, Number0, Number1);
374         BigInt_Negate(&Number0);
375         BigInt_Negate(&Number1);
376         return;
377     }
378     if (BigInt_IsGreaterThan(Number1, Number0))
379     {
380         BigInt_Mul(Result, Number1, Number0);
381         return;
382     }
383     
384     if (Number0.Length<4 || Number1.Length<4)
385         BigInt_SlowMul(Result, Number0, Number1);
386     else
387         BigInt_FastMul(Result, Number0, Number1);
388     return;
389 }
\end{verbatim}
\end{Code}


\hypertarget{BigInt_8h_c32621fd44f345ce54b315ed6f1f310b}{
\index{BigInt.h@{BigInt.h}!BigInt\_\-SlowMul@{BigInt\_\-SlowMul}}
\index{BigInt\_\-SlowMul@{BigInt\_\-SlowMul}!BigInt.h@{BigInt.h}}
\subsubsection[{BigInt\_\-SlowMul}]{\setlength{\rightskip}{0pt plus 5cm}void BigInt\_\-SlowMul (BigInt $\ast$ {\em Result}, \/  BigInt {\em Number0}, \/  BigInt {\em Number1})}}
\label{BigInt_8h_c32621fd44f345ce54b315ed6f1f310b}


Multiples two BigInts together (Number0 and Number1), and stores the result into Result, using the standard multiplication.

\begin{Desc}
\item[Parameters:]
\begin{description}
\item[{\em Result}]A pointer to a Bigint where the result should be stored. \item[{\em Number0}]First number. \item[{\em Number1}]Second number. \end{description}
\end{Desc}
\begin{Desc}
\item[Returns:]\end{Desc}


Definition at line 532 of file BigInt.c.

\begin{Code}\begin{verbatim}533 {
534     if (Number0.IsNegative==true && Number1.IsNegative==false)
535     {
536         BigInt_Negate(&Number0);
537         BigInt_SlowMul(Result, Number0, Number1);
538         BigInt_Negate(Result);
539         BigInt_Negate(&Number0);
540         return;
541     }
542     if (Number0.IsNegative==false && Number1.IsNegative==true)
543     {
544         BigInt_Negate(&Number1);
545         BigInt_SlowMul(Result, Number0, Number1);
546         BigInt_Negate(Result);
547         BigInt_Negate(&Number1);
548         return;
549     }
550     if (Number0.IsNegative==true && Number1.IsNegative==true)
551     {
552         BigInt_Negate(&Number0);
553         BigInt_Negate(&Number1);
554         BigInt_SlowMul(Result, Number0, Number1);
555         BigInt_Negate(&Number0);
556         BigInt_Negate(&Number1);
557         return;
558     }
559     if (BigInt_IsGreaterThan(Number1, Number0))
560     {
561         BigInt_SlowMul(Result, Number1, Number0);
562         return;
563     }
564     
565     BigInt ResultTemp=BigInt_Create();
566     BigInt Number1Backup=BigInt_Create();
567     BigInt_SetFromBigInt(&Number1Backup, Number1);
568     
569     BigInt_SetFromBigInt(Result, Number0);
570     
571     BigInt One=BigInt_Create();
572     BigInt_SetFromInt(&One, 1);
573     
574     while(BigInt_IsGreaterThan(Number1Backup, One))
575     {
576         BigInt_SetFromBigInt(&ResultTemp, *Result);
577         BigInt_Add(Result, ResultTemp, Number0);
578         BigInt_Dec(&Number1Backup);
579     }
580     
581     BigInt_Destroy(Number1Backup);
582     BigInt_Destroy(ResultTemp);
583     BigInt_Destroy(One);
584     
585     BigInt_Clean(Result);
586 }
\end{verbatim}
\end{Code}


